package gameplaying;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//取石子游戏
public class StoneProblem {

	private static final int MAX = 200002;
	
	private int[] stones = new int[MAX];
	
	
	public static void main(String[] args) {
		StoneProblem object = new StoneProblem();
//		object.getRes();
//		object.getResII();
//		object.getResIII();
//		object.getResIV();
//		object.getResV();
		object.getResIII_2();
	}
	
	//m堆中取石子，但是要输出先取的策略
	//根据算法合集之《由感性认识到理性认识——透析一类搏弈游戏的解答过程》
	//我们知道了#S != 0, 存在S -> T, 使得 #T = 0
	//而且我们知道是在第k堆中取sum(异或的和)最高位为1（假设为k），在k位为1那些堆中取。
	//剩下sum ^ (其余堆的异或和)
	//Runtime: 1201MS
	public void getRes(){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int m = scanner.nextInt();
			if(m == 0){
				break;
			}
			int sum = 0;
			for(int i = 0; i < m; i++){
				stones[i] = scanner.nextInt();
				sum ^= stones[i];
			}
			if(sum == 0){
				System.out.println("No");
				continue;
			}else{
				System.out.println("Yes");
			}
			List<Integer> first = getFirst(sum, m);
			int size = first.size();
			for(int i = 0; i < size; i++){
				int remain = first.get(i) ^ sum;
				System.out.println(first.get(i) + " " + remain);
			}
		}
		scanner.close();
	}
	
	public List<Integer> getFirst(int sum, int m){
		List<Integer> res = new ArrayList<>();
		for(int i = 0; i < m; i++){
			//我们所需要找的是(stones[i] ^ sum) < stones[i]
			if( (stones[i] ^ sum) < stones[i]){
				res.add(stones[i]);
			}
		}
		return res;
	}
	
	
	//hdu 1907, 拿到最后一个石子是输者
	//m堆取石子游戏的变形,anti-Nim
	@Deprecated
	public void getResIIWrong(){
		Scanner scanner = new Scanner(System.in);
		int testCase = scanner.nextInt();
		for(int t = 1; t <= testCase; t++){
			int m = scanner.nextInt();
			if(m == 0){
				break;
			}
			int sum = 0;
			for(int i = 0; i < m; i++){
				stones[i] = scanner.nextInt();
				sum ^= stones[i];
			}
			//我们可以想象多了一堆只有一个的石子，这样谁拿到最后的石子为胜者仍然适用
			//但是最后的异或结果还要异或1，先前为0表示必输，此时为1
			//先前为非0表示有获胜策略，此时为非1
			//思路错了：比如 2 2是先手必败的场面，如果按照上面说的
			// 2 2 1，此时异或结果为1，说明在原始规则下，先手必胜
			//但是如果按照我们说的，异或结果为1，表示先手必输。但是实际不是这样的
			//我们先拿1的那一堆，此时剩 2  2，后者拿1个或两个，我将另一堆的拿两个或一个，后者必败
			if(sum == 1){
				System.out.println("Brother");
			}else{
				System.out.println("John");
			}
		}
		scanner.close();
	}
	
	//HDU 1907 和 2509
	// 重新设置状态：http://blog.csdn.net/fsss_7/article/details/51374659
	// 设糖果数为1的叫孤独堆，糖果数大于1的叫充裕堆，设状态S0：a1^a2^..an != 0 && 充裕堆堆数  = 0，
	// 则先手必败（奇数个为1的堆，先手必败）
	// S1：充裕堆堆数 = 1，则先手必胜（若剩下的n-1个孤独堆个数为奇数个，那么将那个充裕堆全部拿掉，
	// 否则将那个充裕堆拿得只剩一个，这样的话先手必胜）
	// T0：a1^a2^..an = 0 && 充裕堆堆数  = 0，先手必胜（只有偶数个孤独堆，先手必胜）
	// S2：a1^a2^..an!=0 && 充裕堆堆数 >= 2。T2：a1^a2^..an = 0 && 充裕堆堆数  >= 2。
	// （a）S2可以取一次变为T2。 （b）T2取一次变为S2或者S1
	//根据b规则，当T2由两堆相同的组成时，如果此时变成S2，即两堆的石子个数大于1
	//那么我们在另一堆里面继续取相同数目，使得变为T2，最后导致T2只有S1局面可走
	//因为S1是先手必胜，所以此时我们赢了。故T2先手必败
	//因为S2存在到T2的局面，所以先手必胜
	// Runtime : 358MS
	public void getResII(){
		Scanner scanner = new Scanner(System.in);
		int testCase = scanner.nextInt();
		for(int t = 1; t <= testCase; t++){
			int m = scanner.nextInt();
			if(m == 0){
				break;
			}
			int sum = 0;
			//记录充裕堆的数目
			int abundantCount = 0;
			for(int i = 0; i < m; i++){
				stones[i] = scanner.nextInt();
				sum ^= stones[i];
				if(stones[i] > 1){
					abundantCount++;
				}
			}
			//必败有充裕堆数目为0，异或结果不为0和充裕堆数目大于等于2，异或结果为0
			if(sum != 0 && abundantCount == 0 || (sum == 0 && abundantCount > 1)){
				System.out.println("Brother");
			}else{
				//必胜是充裕堆数目为0，异或结果为0(偶数个孤独堆)
				//或者充裕堆数目大于等于1，异或结果不为0
				//注意，充裕堆的堆数为1的时候，比如2 1 1....
				//此时异或结果肯定不为0
				System.out.println("John");
			}
		}
		scanner.close();
	}
	
	//HDU 1527
	// 威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同
	// 时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
	public void getResIII(){
		Scanner scanner = new Scanner(System.in);
		double k = (Math.sqrt(5) + 1 ) / 2;
		while(scanner.hasNext()){
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			int t = 0;
			if(a > b){
				t = a;
                a = b;
                b = t;
			}
			t = b - a;
            int ak = (int) (t * k);
			if (a == ak)
				System.out.println("0");
			else
				System.out.println("1");
		}
		scanner.close();
	}
	
	//还是跟上面一样的，但是输入很大，到10^100
	public void getResIV(){
		Scanner scanner = new Scanner(System.in);
		//wrong answer
		//因为输入很大，所以黄金分割数必须精确到小数点后100位，否则会导致计算错误
		double k = (Math.sqrt(5) + 1 ) / 2;
		BigDecimal kDecimal = new BigDecimal(k);
		while(scanner.hasNext()){
			String a = scanner.next();
			String b = scanner.next();
			if(a.equals("0") || b.equals("0")){
				if(a.equals("b")){
					System.out.println("0");
				}else{
					System.out.println("1");
				}
				continue;
			}
			BigDecimal t = new BigDecimal(0);
			if(a.compareTo(b) > 0){
				String temp = a;
                a = b;
                b = temp;
			}
			BigInteger aInteger = new BigInteger(a);
			
			BigDecimal aDecimal = new BigDecimal(a);
			BigDecimal bDecimal = new BigDecimal(b);
			t = bDecimal.subtract(aDecimal);
			BigInteger ak = t.multiply(kDecimal).toBigInteger();
			if (aInteger.equals(ak))
				System.out.println("0");
			else
				System.out.println("1");
		}
		scanner.close();
	}
	
	//斐波那契博弈
	//HDU 2516 Runtime ：265MS
	public void getResV(){
		Scanner scanner = new Scanner(System.in);
		//因为斐波那契数列的第44项是1134903170, 45 项是1836311903
		int[] fibonaqi = new int[50];
		fibonaqi[0] = 1;
		fibonaqi[1] = 2;
		for(int i = 2; i < 45; i++){
			fibonaqi[i] = fibonaqi[i - 1] + fibonaqi[i - 2]; 
		}
		System.out.println(fibonaqi[44] + " " + fibonaqi[43]);
		while(scanner.hasNext()){
			int n = scanner.nextInt();
			if(n == 0){
				break;
			}
			boolean win = true;
			//当n为斐波那契数的时候是必败点
			for(int i = 0; i < 45; i++){
				if(n == fibonaqi[i]){
					win = false;
					break;
				}
			}
			if(win){
				System.out.println("First win");
			}else{
				System.out.println("Second win");
			}
		}
		scanner.close();
	}
	
	
	private static final int MAX_2 = 700002;
	
	private int[] initialX = new int[MAX_2];
	private int[] initialY = new int[MAX_2];
	
	//威佐夫博奕,求怎样取
	//Runtime: 327MS
	public void getResIII_2(){
		Scanner scanner = new Scanner(System.in);
		double k = (Math.sqrt(5) + 1 ) / 2;
		for(int i = 1; i < MAX_2; i++){
			initialX[i] = (int) (i * k); 
			initialY[i] = initialX[i] + i; 
		}
		while(scanner.hasNext()){
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			if(a == 0 && b == 0){
				break;
			}
			int t = b - a;
            int ak = (int) (t * k);
			if (a == ak){
				System.out.println("0");
			}else{
				System.out.println("1");
				int index = binarySearch(initialX, 0, initialX.length - 1, a);
				//如果a = ak
				if(initialX[index] == a){
					if(initialY[index] < b){
						//此时只有一种情况,那就是取到(a, initialY[index])
						System.out.println(a + " " + initialY[index]);
						continue;
					}else{
						//如果bk大于b，则有取两堆的情况
						System.out.println(initialX[b - a] + " " + initialY[b - a]);
						//之后再搜索y中是否有b
						int indexB = binarySearch(initialY, 0, index + 1, b);
						if(initialY[indexB] == b){
							System.out.println(initialX[indexB] + " " + b);
						}
					}
				}else{
					// a大于ak
					//首先我们知道a在bz中肯定存在
					int indexB = binarySearch(initialY, 0, index + 1, a);
					//fromB表示(b – m,  a)的b - m
					int fromB = initialX[indexB];
//					if(initialY[indexB] == a){
//						fromB = initialX[indexB];
//						System.out.println(fromB + " " + a);
//					}
					//如果b - a > k,那么肯定是不会有取两堆或者取a堆的情况
					if(b - a > index){
						System.out.println(fromB + " " + a);
						continue;
					}else{
						//取两堆的情况
						System.out.println(initialX[b - a] + " " + initialY[b - a]);
						
						//在判断b是否在y数组中出现
						int indexBOfb = binarySearch(initialY, 0, index + 1, b);
						//如果出现
						if(initialY[indexBOfb] == b){
							System.out.println(initialX[indexBOfb] + " " + b);
						}
					}
					//还需要注意a == b的情况
					if(initialX[b - a] != fromB && a != b){
						System.out.println(fromB + " " + a);
					}
				}
			}
		}
		scanner.close();
	}
	
	//找到最大的小于等于target的下标
	public int binarySearch(int[] nums, int left, int right, int  target){
		if(left < 0 || right >= MAX_2){
			return -1;
		}
		int middle;
		while(left < right){
			middle = (right + left + 1) / 2;
			if(nums[middle] <= target){
				left = middle;
			}else{
				right = middle - 1;
			}
		}
		return left;
	}
	
	
	//最简单的巴什博弈 HDU1846
	public void getResBaShi(){
		Scanner scanner = new Scanner(System.in);
		int testCase = scanner.nextInt();
		for (int t = 1; t <= testCase; t++) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			if(n % (m + 1) == 0){
				System.out.println("second");
			}else{
				System.out.println("first");
			}
		}
		scanner.close();
	}
	
	//变形的巴什博弈  HDU1847
	//只能取2的幂次，可以证明，必败态为3的倍数
	//这个证明在数学归纳法中的递归过程是如果前面k个分别是3的1....k倍，那么第k + 1个是3的k + 1倍
	//Runtime：374MS
	public void getResBaShiII(){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int n = scanner.nextInt();
			if(n % 3 == 0){
				System.out.println("Cici");
			}else{
				System.out.println("Kiki");
			}
		}
		scanner.close();
	}
}
